package LeetCode热题HOT100;

public class p33搜索旋转排序数组 {
    public int search(int[] nums, int target) {
        //二分查找，找旋转点是关键，在有序的区间找target，有序区间依赖mid和right的比较
        int left=0;
        int right=nums.length-1;

        while (left<=right) {
            int mid=(left+right)/2;

            if (nums[mid]==target) {
                return mid;
            }else if (nums[mid] < nums[right]) {
                //[mid-right] 有序
                if (nums[mid]<target && target<=nums[right]) {
                    left=mid+1;
                }else {
                    right=mid-1;
                }

            }else {
                //[left-mid] 有序
                if (nums[left]<=target && target<nums[mid]) {
                    right=mid-1;
                }else {
                    left=mid+1;
                }
            }

        }
        return -1;

    }


    public int search1(int[] nums, int target) {
        //暴力解法
        for (int i = 0; i <nums.length ; i++) {
            if (target==nums[i]) {
                return i;
            }
        }
        return -1;
    }
}
